package tree.leetcode_230_medium;

public class DivideSolution {
    /*
        记录左子树节点个数为n，如果n + 1 = k，则根节点就是结果
        如果n + 1 < k， 则说明第k小的数不在左子树中，递归寻找右子树
        如果n + 1 > k， 则说明第k小的树不在右子树中，递归寻找左子树
     */
    public int kthSmallest(TreeNode root, int k) {
        if(root == null){
            return 0;
        }
        int n = count(root.left);
        if(n + 1 == k){
            return root.val;
        }else if(n + 1 < k){
            return kthSmallest(root.right,k - n - 1);
        }else{
            return kthSmallest(root.left, k);
        }
    }
    public int count(TreeNode root){
        if(root == null){
            return 0;
        }
        return 1 + count(root.left) + count(root.right);
    }
}
